package leetcode101_xqzhao

// TODO 全排列 【-】 递归+回溯

func permute(nums []int) [][]int {
	n := len(nums)
	res := make([][]int, 0)
	path := make([]int, 0)
	visited := make(map[int]bool, n)

	var dfs046 func(length int)
	dfs046 = func(length int) {
		// 递归结束控制器 + 保存结果
		if length == n {
			tmpPath := make([]int, length)
			copy(tmpPath, path)
			res = append(res, tmpPath)
			return
		}
		for i := 0; i < n; i++ {
			if visited[nums[i]] {
				continue
			}
			path = append(path, nums[i])
			visited[nums[i]] = true
			dfs046(length + 1)
			// 回溯
			path = path[:len(path)-1]
			visited[nums[i]] = false
		}
	}

	dfs046(0)
	return res
}
